package com.problem.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yanzhuoleo
 * @version V1.0
 * @Description: Problem46
 * @date 2018-01-08-下午2:50
 */

public class Problem46 {
    public List<List<Integer>> permute(int[] num) {
        List<List<Integer>> res = new ArrayList<List<Integer>>() {};
        if (num == null || num.length == 0) {
            return res;
        }
        helper(num, new boolean[num.length], new ArrayList<Integer>(), res);
        return res;
    }

    private void helper(int[] num, boolean[] used, ArrayList<Integer> item,
                        List<List<Integer>> res) {
        if (item.size() == num.length) {
            res.add(new ArrayList<Integer>(item));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (!used[i]) {
                used[i] = true;
                item.add(num[i]);
                helper(num, used, item, res);
                item.remove(item.size() - 1);
                used[i] = false;
            }
        }
    }

}
